package com.wxit.algorithm.leetcode;

/**
 * 删除有序链表重复节点
 */
public class E04LeetCode83 {

    /**
     * 方法1： 双指针法
     * @param head
     * @return
     */
    public ListNode deleteDuplicates01(ListNode head) {
        //小于两个节点的情况
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2;
        while ((p2 = p1.next) != null) {
            if (p1.val == p2.val) {
                //删除p2节点
                p1.next = p2.next;
            } else {
                //向后平移
                p1 = p1.next;
            }
        }
        return head;
    }

    /**
     * 方法2：递归法
     * @param p
     * @return
     */
    public ListNode deleteDuplicates(ListNode p) {
       if (p == null || p.next == null) {
           return p;
       }
       if (p.val == p.next.val) {
           return deleteDuplicates(p.next);
       } else {
           p.next = deleteDuplicates01(p.next);
           return p;
       }
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 1, 2);
        System.out.println(head);
        System.out.println(new E04LeetCode83().deleteDuplicates(head));
    }
}
